import csv
import random
import math
import operator


def load_dataset(filename, split, training_set=[], test_set=[]):
    """
    加载数据集并将其分为训练集和测试集
    """
    with open(filename, 'r') as csvfile:
        lines = csv.reader(csvfile)
        dataset = list(lines)
        for x in range(len(dataset) - 1):
            for y in range(4):
                dataset[x][y] = float(dataset[x][y])
            if random.random() < split:
                training_set.append(dataset[x])
            else:
                test_set.append(dataset[x])


def euclidean_distance(instance1, instance2, length):
    """
    计算两个实例之间的欧氏距离
    """
    distance = 0
    for x in range(length):
        distance += pow((instance1[x] - instance2[x]), 2)
    return math.sqrt(distance)


def get_neighbors(training_set, test_instance, k):
    """
    找到测试实例的k个最近邻
    """
    distances = []
    length = len(test_instance) - 1
    for x in range(len(training_set)):
        dist = euclidean_distance(test_instance, training_set[x], length)
        distances.append((training_set[x], dist))
    distances.sort(key=operator.itemgetter(1))
    neighbors = []
    for x in range(k):
        neighbors.append(distances[x][0])
    return neighbors


def get_response(neighbors):
    """
    根据邻居的投票确定测试实例的类别
    """
    class_votes = {}
    for x in range(len(neighbors)):
        response = neighbors[x][-1]
        if response in class_votes:
            class_votes[response] += 1
        else:
            class_votes[response] = 1
    sorted_votes = sorted(class_votes.items(), key=operator.itemgetter(1), reverse=True)
    return sorted_votes[0][0]


def get_accuracy(test_set, predictions):
    """
    计算预测准确率
    """
    correct = 0
    for x in range(len(test_set)):
        if test_set[x][-1] == predictions[x]:
            correct += 1
    return (correct / float(len(test_set))) * 100.0


def main():
    # 准备数据
    training_set = []
    test_set = []
    split = 0.67  # 训练集占比
    load_dataset('iris.data', split, training_set, test_set)
    print('训练集大小: ' + repr(len(training_set)))
    print('测试集大小: ' + repr(len(test_set)))

    # 生成预测
    predictions = []
    k = 3  # 近邻数量
    for x in range(len(test_set)):
        neighbors = get_neighbors(training_set, test_set[x], k)
        result = get_response(neighbors)
        predictions.append(result)
        print('> 预测=' + repr(result) + ', 实际=' + repr(test_set[x][-1]))

    # 计算准确率
    accuracy = get_accuracy(test_set, predictions)
    print('准确率: ' + repr(accuracy) + '%')


if __name__ == '__main__':
    main()
